package algorithm.Strings;

/**
 * @Author: 李浩然
 * @Date: 2021/1/6 9:58 上午
 */
public class longestPublicSubSequence {
    /**
     * 最长公共子序列，返回值为长度
     *
     * @param a
     * @param b
     * @return
     */
    static int longestPublicSubSequence(String a, String b) {
        if (a.length() == 0 || b.length() == 0) return 0;
        if (a.charAt(0) == b.charAt(0)) return longestPublicSubSequence(a.substring(1), b.substring(1)) + 1;
        return Math.max(longestPublicSubSequence(a.substring(0), b.substring(1)), longestPublicSubSequence(a.substring(1), b.substring(0)));
    }

    public static int longestCommonSubsequence(String text1, String text2) {
        if (text1.length() == 0 || text2.length() == 0 || text1 == null || text2 == null) {
            return 0;
        }
        int length1 = text1.length();
        int length2 = text2.length();
        int[][] dp = new int[length1 + 1][length2 + 1];
        /*
            遍历两个字符串:
                1、若 当前两个字符 相等：
                    当前状态 = 两个元素的前一个状态 + 1
                2、若 当前两个字符 不等：
                    当前状态 = 两个元素任一元素的前一个状态 的 最大值
         */
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (chars1[i - 1] == chars2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[length1][length2];
    }

    public static void main(String[] args) {
        int res = longestCommonSubsequence("abacd", "abc");
        System.out.println(res);
    }
}
